// 和上题相比，这里最多有k笔交易
// 除了0次交易，每奇数次交易是买入，每偶数次交易是卖出，所以一共了k次交易，那么j的范围定义到2*k + 1即可
// 五部曲
// 1. `dp[i][j]`, 表示第i天状态j所剩下的最大现金，除了0天，偶数天表示不持有股票，奇数天表示持有股票，j的范围定义为 `2 * k + 1`即可
// 2. 递推公式
// ```js
// for(let j = 0; j < 2 * k - 1;j += 2) {
//     dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i])
//     dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
// }
// ```
// 3. 初始化，
// ```js
// for(let j = 1; j < 2 * k; j+=2) {
//     dp[0][j] = -prices[0]
// }
// ```
// 4. 遍历顺序
// 5. 推导


// 时间复杂度: O(n * k)，其中 n 为 prices 的长度
// 空间复杂度: O(n * k)

function maxProfit(k, prices) {
    let dp = new Array(prices.length).fill(0).map(_ => new Array(2 * k + 1).fill(0)) 
    for (let j = 1; j < 2 * k; j += 2) {
        dp[0][j] = -prices[0]
    }
    for (let i = 1; i < prices.length; i++) {
        for (let j = 0; j < 2 * k - 1; j += 2) {
            dp[i][j + 1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i])  
            dp[i][j + 2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])          
        }        
    }
    return dp[prices.length - 1][2 * k]
}

let k = 2, prices = [3,2,6,5,0,3]
console.log(maxProfit(k, prices))
console.log(maxProfit(2, [3,3,5,0,0,3,1,4]))